// Copyright (C) Calum Grant 2008

#include <cppscript>

var test(var description, var fn);

var int_sum(var max)
{
	var total=0;
	foreach( i, range(1,max) ) total += i;
	return total;
}

var dbl_sum(var max)
{
	var total=0.0;
	foreach( i, range(1,max) ) total += i;
	return total;
}

var tree(var item, var depth) 
{
	if(depth) 
	{
		--depth;
		var item2 = item * 2;
		return array( item, tree(item2-1, depth), tree(item2, depth) );
	}
	else
		return item;
}

var check_tree_object(var node)
{
	return node["item"] + node["left"]["check"]() - node["right"]["check"]();
}

var check_leaf(var node)
{
	return node["item"];
}

var tree_object(var item, var depth)
{
	return depth 
		?
		object("tree").extend
			("item",item)
			("left",tree_object(item*2-1,depth-1))
			("right",tree_object(item*2,depth-1))
			("check",check_tree_object)
		:
		object("leaf").extend
			("item",item)
			("check",check_leaf);
}

var check_tree(var tree)
{
	return tree.size() ? tree[0] + check_tree(tree[1]) - check_tree(tree[2]) : tree;
}

void binary_trees(var max_depth)
{
	var min_depth=4;
	// var max_depth = max(min_depth, args[1].as_int());
	var stretch_depth = max_depth+1;
	writeln("stretch tree of depth " + stretch_depth + "\tcheck: " + check_tree(tree(0, stretch_depth)) );

	var long_lived_tree = tree(0, max_depth.as_int());

	foreach( d, range(min_depth, max_depth, 2))
	{
		var iterations=1<<(max_depth-d+min_depth).as_int(), c=0;
		foreach( i, range(1,iterations) )
		{
			var a = tree(i, d), b = tree(-i, d);
			c += check_tree(a) + check_tree(b);
		}

		writeln( "" + iterations*2 + "\ttrees of depth " + d + "\tcheck: " + c );
	}

	writeln("long lived tree of depth " + max_depth + "\tcheck: " + check_tree(long_lived_tree) );
}

void binary_trees_using_object(var max_depth)
{
	var min_depth=4;
	var stretch_depth = max_depth+1;
	writeln("stretch tree of depth " + stretch_depth + "\tcheck: " + tree_object(0,stretch_depth)["check"]() );

	var long_lived_tree = tree_object(0, max_depth.as_int());

	foreach( d, range(min_depth, max_depth, 2))
	{
		var iterations=1<<(max_depth-d+min_depth).as_int(), c=0;
		foreach( i, range(1,iterations) )
		{
			var a = tree_object(i, d), b = tree_object(-i, d);
			c += check_tree_object(a) + check_tree_object(b);
		}

		writeln( "" + iterations*2 + "\ttrees of depth " + d + "\tcheck: " + c );
	}

	writeln("long lived tree of depth " + max_depth + "\tcheck: " + check_tree_object(long_lived_tree) );
}

var tests()
{
	return map
		("intsum", test("Sums the numbers 1 to 1000000 using ints", bind(int_sum,1000000)))
		("dblsum", test("Sums the numbers 1 to 1000000 using doubles", bind(dbl_sum,1000000)))
		("tree10", test("Build binary trees of depth 10", bind(binary_trees, 10)))
		("tree14", test("Build binary trees of depth 14", bind(binary_trees, 14)))
		("treeobject", test("Build binarytrees using objects", bind(binary_trees_using_object, 10)))
		;
}
